home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / queue.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  1.9 KB  |  65 lines
  1. {\magonebf 3.4 Queues (queue)  }
  2.  
  3. \decl  queue E 
  4.  
  5. {\bf 1. Definition}
  6.  
  7. An instance $Q$ of the parameterized data type \name\ is 
  8. a sequence of elements of data type $E$, called the element 
  9. type of $Q$. Elements are inserted at one end (the rear) and deleted at the 
  10. other end (the front) of $Q$. The size of $Q$ is the length of the sequence, 
  11. a queue of size zero is called the empty queue.
  12.  
  13.  
  14. \bigskip
  15. {\bf 2. Creation}
  16.  
  17. \create Q {}
  18.  
  19. creates an instance \var\ of type \name. \var\ is initialized with the empty 
  20. queue.
  21.  
  22.  
  23. \bigskip
  24. {\bf 3. Operations}
  25. \+\cleartabs & \hskip 2truecm & \hskip 4truecm &\cr
  26. \+\op E     top    {}       
  27.                             { returns the front element of \var}
  28. \+\nop                      { \precond $Q$ is not empty.}
  29. \smallskip
  30. \+\op E     pop    {}       
  31.                             { deletes and returns the front element of \var}
  32. \+\nop                      { \precond $Q$ is not empty.}
  33. \smallskip
  34. \+\op void  append {E\ x}   
  35.                             { appends $x$ to the rear end of \var.}
  36. \smallskip
  37. \+\op void  clear  {}       
  38.                             { makes \var\ the empty queue.}
  39. \smallskip
  40. \+\op int   size   {}       
  41.                             { returns the size of \var.}
  42. \smallskip
  43. \+\op bool  empty  {}       
  44.                             { returns true if \var\ is empty, false otherwise.}
  45.  
  46. \bigskip
  47. {\bf 4. Implementation}
  48.  
  49. Queues are implemented by singly linked linear lists. All operations take time 
  50. $O(1)$, except clear which takes time $O(n)$, where $n$ is the size of the 
  51. queue.
  52.  
  53.  
  54. %\bigskip
  55. %{\bf 5. Bounded Queues}
  56. %
  57. %Bounded queues (b\_queues) are queues of bounded size. 
  58. %\medskip
  59. %\+\cleartabs
  60. %  Declaration: &{\bf declare}($b\_queue,E$) \cr
  61. %\+Creation:    &$b\_queue(E)$ $Q(n)$; \cr
  62. %\+             &creates an instance $Q$ of type $b\_queue(E)$ that can hold up to $n$ elements.\cr
  63. %\+Operations:  &see queue\cr
  64. %
  65.